package com.cheng.dataStructure.tree;

/**
 * @User Administrator
 * @Classname BinaryTreeDemo
 * @Project Data-structure-and-algorithm
 * @Description 删除二叉树节点
 * 要求：1)如果删除的节点是叶子节点，则删除该节点
 *      2)如果删除的节点是非叶子节点，则删除该子树.
 * 思路：1、考虑如果是空树，则将二叉树置空
 *      2、因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除，而不能去判断当前这个结点是不是需要删除.
 *      3、如果当前结点的左子结点不为空，并且左子结点就是要删除的结点，就将this.left=null;并且返回
 *      4、如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null;并且返回
 *      4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
 *      5．如果第4步也没有删除结点,则应当向右子树进行递归删除.
 *
 * @Author wpcheng
 * @Create 2021-08-21-9:54
 * @Version 1.0
 */
public class BinaryTreeDelete {
    public static void main(String[] args) {

        //创建二叉树
        BinaryTree2 binaryTree = new BinaryTree2();
        //定义节点
        HeroNode2 root = new HeroNode2(1, "刘备");
        HeroNode2 node2 = new HeroNode2(2, "关羽");
        HeroNode2 node3 = new HeroNode2(3, "张飞");
        HeroNode2 node4 = new HeroNode2(4, "黄忠");
        HeroNode2 node5 = new HeroNode2(5, "马超");
        HeroNode2 node6 = new HeroNode2(6, "墨子");
        HeroNode2 node7 = new HeroNode2(7, "干将");
        //把节点插入到树中
        root.setLeft(node2);
        root.setRight(node3);
        node2.setRight(node4);
        node3.setRight(node5);
        node2.setLeft(node6);
        node4.setLeft(node7);

        binaryTree.setRoot(root);

        System.out.println("删除前的前序遍历");
        binaryTree.preOrder();
        binaryTree.delNode(4);
        System.out.println("删除后的前序遍历");
        binaryTree.preOrder();



    }

}

//定义二叉树BinaryTree
class BinaryTree2 {
    private HeroNode2 root;

    public void setRoot(HeroNode2 root) {
        this.root = root;
    }

    public void delNode(int id){
        if (root != null){
            if (root.getId() == id){
                root = null;
            }else{
                root.delNode(id);
            }
        }else {
            System.out.println("树为空");
        }
    }

    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("树为空");
        }
    }

    //中序遍历
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("树为空");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("树为空");
        }
    }

    //前序查找
    public HeroNode2 preOrderSearch(int id) {
        if (this.root != null) {
            return this.root.preOrderSearch(id);
        } else {
            return null;
        }
    }

    //中序查找
    public HeroNode2 infixOrderSearch(int id) {
        if (this.root != null) {
            return this.root.infixOrderSearch(id);
        } else {
            return null;
        }
    }

    //后序查找
    public HeroNode2 postOrderSearch(int id) {
        if (this.root != null) {
            return this.root.postOrderSearch(id);
        } else {
            return null;
        }
    }
}

//定义二叉树的节点
class HeroNode2 {
    private int id;
    private String name;
    private HeroNode2 left;
    private HeroNode2 right;

    public HeroNode2(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode2 getLeft() {
        return left;
    }

    public void setLeft(HeroNode2 left) {
        this.left = left;
    }

    public HeroNode2 getRight() {
        return right;
    }

    public void setRight(HeroNode2 right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    //编写前序遍历方法
    public void preOrder() {
        //先输出父节点
        System.out.println(this);

        if (this.left != null) {
            this.left.preOrder();//以左节点为父节点开始递归
        }
        if (this.right != null) {
            this.right.preOrder();//以右节点为父节点开始递归
        }
    }

    //编写中序遍历方法
    public void infixOrder() {

        if (this.left != null) {
            this.left.preOrder();//以左节点为父节点开始递归
        }
        //输出父节点
        System.out.println(this);

        if (this.right != null) {
            this.right.preOrder();//以右节点为父节点开始递归
        }
    }

    //编写后序遍历方法
    public void postOrder() {

        if (this.left != null) {
            this.left.preOrder();//以左节点为父节点开始递归
        }

        if (this.right != null) {
            this.right.preOrder();//以右节点为父节点开始递归
        }
        //输出父节点
        System.out.println(this);
    }

    //前序查找
    public HeroNode2 preOrderSearch(int id) {
        //先比较当前节点，如果当前节点是要找的节点，则直接返回
        if (this.id == id) {
            return this;
        }
        HeroNode2 resNode = null;
        //如果不是，再判断左节点是否为空，若不为空，就向左节点递归查找
        if (this.left != null) {
            resNode = this.left.preOrderSearch(id);
        }
        //若左节点递归查到，就返回
        if (resNode != null) {
            return resNode;
        }
        //若左节点递归没查到，就向右节点递归查找
        if (this.right != null) {
            resNode = this.right.preOrderSearch(id);
        }
        //向右节点递归查找后，查到就返回，查不到就返回null
        return resNode;
    }

    //中序查找
    public HeroNode2 infixOrderSearch(int id) {

        HeroNode2 resNode = null;
        //先判断左节点是否为空，若不为空，就向左节点递归查找
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(id);
        }
        //若左节点递归查到，就返回
        if (resNode != null) {
            return resNode;
        }
        //若左节点递归没查到，就比较当前节点，如果当前节点是要找的节点，则直接返回
        if (this.id == id) {
            return this;
        }
        //若左节点递归没查到，就向右节点递归查找
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(id);
        }
        //向右节点递归查找后，查到就返回，查不到就返回null
        return resNode;
    }

    //后序查找
    public HeroNode2 postOrderSearch(int id) {

        HeroNode2 resNode = null;
        //先判断左节点是否为空，若不为空，就向左节点递归查找
        if (this.left != null) {
            resNode = this.left.postOrderSearch(id);
        }
        //若左节点递归没查到，就比较当前节点，如果当前节点是要找的节点，则直接返回
        if (this.id == id) {
            return this;
        }
        //若左节点递归没查到，就向右节点递归查找，查到就直接返回
        if (this.right != null) {
            resNode = this.right.postOrderSearch(id);
        }

        //向右节点递归没查找，就比较当前节点，如果找的，则直接返回，不是就返回null
        if (resNode != null) {
            return this;
        }
        return resNode;

    }

    //删除节点
    public void delNode(int id){
        if (this.left != null && this.left.id == id){
            this.left = null;
            return;
        }
        if (this.right != null && this.right.id == id){
            this.right = null;
            return;
        }
        if (this.left != null){
            this.left.delNode(id);
        }
        if (this.right != null){
            this.right.delNode(id);
        }
    }








}